package com.jack.leetcode.test;

import java.util.Arrays;

public class 替换所有的问号 {

    public static void main(String[] args) {
        System.out.println(modifyString("?zs"));
        System.out.println(modifyString("ubv?w"));
        System.out.println(modifyString("?ubv?w"));
        System.out.println(modifyString("j?qg??b"));
        System.out.println(modifyString("??yw?ipkj?"));
        System.out.println(modifyString("????"));
        System.out.println(modifyString("wz???a??n"));
        System.out.println(modifyString("v????gm??a?czgn?ba?dya?????b?t????j??ag??qm?????t?imx?f??gc??a????orb??e?uvae?ak?????a?e??f??qg"));
        System.out.println(modifyString("????????????????????????????????????????????????????????????????????????????????????????????????????"));
    }

    public static String modifyString(String s) {
        int n = s.length();
        Character begin = null, end = null;
        int index = 0;
        int[] dp = new int[26];
        char[] chars = s.toCharArray();
        while(index < n){
            char cur = chars[index];
            if(cur == '?'){
                int left = index;
                while(index < n && chars[index] == '?'){
                    index++;
                }
                int right = index - 1;
                for(int i = left;i <= right;i++){
                    begin = i == 0 ? null : chars[i - 1];
                    end = i == n - 1 || chars[i + 1] == '?' ? null : chars[i + 1];
                    Arrays.fill(dp, 0);
                    if(begin != null){
                        dp[begin - 'a']++;
                    }
                    if(end != null){
                        dp[end - 'a']++;
                    }
                    int dpIndex = 0;
                    while(dpIndex < 26 && dp[dpIndex] > 0){
                        dpIndex++;
                    }
                    chars[i] = (char) (dpIndex + 'a');
                }
                continue;
            }
            index++;
        }
        return String.valueOf(chars);
    }
}
